/*
 * @lc app=leetcode.cn id=491 lang=typescript
 *
 * [491] 递增子序列
 */

// @lc code=start

function findSubsequences(nums: number[]): number[][] {
  const result: number[][] = [];
  const hash = new Set();
  const size = nums.length;

  const backtrack = (index: number, path: number[]): void => {
    if (path.length > 1) {
      const key = path.toString();
      if (!hash.has(key)) {
        result.push([...path]);
        hash.add(key);
      }
    }

    if (index === size) {
      return;
    }

    for (let i = index; i < size; i++) {
      if (path.length === 0 || path[path.length - 1] <= nums[i]) {
        // 选择
        path.push(nums[i]);
        // 递归
        backtrack(i + 1, path);
        // 回溯
        path.pop();
      }
    }
  };

  backtrack(0, []);

  return result;
}
// @lc code=end
